package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:删除子数组的最大得分
 *
 * 给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
 * 返回 只删除一个 子数组可获得的 最大得分 。
 * 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
 *
 * 示例 1：
 * 输入：nums = [4,2,4,5,6]
 * 输出：17
 * 解释：最优子数组是 [2,4,5,6]
 *
 * 示例 2：
 * 输入：nums = [5,2,1,2,5,2,1,2,5]
 * 输出：8
 * 解释：最优子数组是 [5,2,1] 或 [1,2,5]
 *
 * 提示：
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^4
 * <p>
 * User:Mr.Du
 * Date:2024/3/29
 * Time:17:14
 */
public class MaximumUniqueSubarray {
    /**
     * 计算数组中最大的不含重复元素的子数组和
     * @param nums 整数数组
     * @return 最大的不含重复元素的子数组和
     */
    public int maximumUniqueSubarray(int[] nums) {
        // 使用布尔数组cnt来记录数字是否出现过，下标对应数字的值
        boolean[] cnt = new boolean[10001];
        int ans = 0; // 存储最大子数组和
        // 双指针l和r维护一个滑动窗口，tmp记录窗口内数字的和
        for (int l = 0, r = 0, tmp = 0; r < nums.length; r++) {
            tmp += nums[r]; // 窗口右端点的数字加入窗口
            // 如果当前数字已经存在于窗口内，则从窗口左端移除数字，直到当前数字不再重复
            while (cnt[nums[r]]) {
                tmp -= nums[l]; // 移除窗口左端点的数字
                cnt[nums[l++]] = false; // 标记该数字为未出现
            }
            cnt[nums[r]] = true; // 标记当前数字为已出现
            ans = Math.max(ans, tmp); // 更新最大子数组和
        }
        return ans; // 返回最大子数组和
    }

    /**
     * 计算数组中最大的不含重复元素的子数组和
     *
     * @param nums 整数数组
     * @return 最大的不含重复元素的子数组和
     */
    public int maximumUniqueSubarray1(int[] nums) {
        int n = nums.length; // 数组长度
        int r = 0, l = 0, res = 0, cnt = 0; // r和l指针，res存储最大和，cnt记录当前子数组的和
        int[] dp = new int[10000+1]; // 动态规划数组，dp[i]表示数字i出现的次数

        while(r < n){ // r遍历数组
            cnt += nums[r]; // 更新当前子数组的和
            dp[nums[r]]++; // 数字出现次数加一
            if(dp[nums[r]] > 1){ // 如果当前数字出现次数大于1，说明有重复元素
                // 移动l指针，直到找到重复元素或者子数组无元素
                while(nums[r] != nums[l]){
                    dp[nums[l]] = 0; // 移除l指针对应的数字
                    cnt -= nums[l++]; // 减去移除的数字的值
                }
                cnt -= nums[l]; // 移除重复的数字
                dp[nums[l++]] = 1; // 重置重复数字的计数为1
            }
            r++; // r指针右移
            res = Math.max(res, cnt); // 更新最大和
        }
        return res; // 返回最大和
    }

}
